// 将元素转换成字符串形式
function defaultToString(item) { 
  if (item === null) { 
    return 'NULL'; 
  } else if (item === undefined) { 
    return 'UNDEFINED'; 
  } else if (typeof item === 'string' || item instanceof String) { 
    return `${item}`; 
  } 
  return item.toString();
}

// 为了在字典中保存 value，我们将 key 转化为了字符串，而为了保存信息的需要，我们同样要保存原始的 key。
// 因此，我们不是只将 value 保存在字典中，而是要保存两个值：原始的key 和 value。
// 为了字典能更简单地通过 toString 方法输出结果，我们同样要为 ValuePair类创建 toString 方法
class ValuePair { 
  constructor(key, value) { 
    this.key = key; 
    this.value = value; 
  } 
  toString() { 
    return `[#${this.key}: ${this.value}]`; 
  } 
 }

/**
 * set(key,value)：向字典中添加新元素。如果 key 已经存在，那么已存在的 value 会被新的值覆盖。
 * remove(key)：通过使用键值作为参数来从字典中移除键值对应的数据值。
 * hasKey(key)：如果某个键值存在于该字典中，返回 true，否则返回 false。
 * get(key)：通过以键值作为参数查找特定的数值并返回。
 * clear()：删除该字典中的所有值。
 * size()：返回字典所包含值的数量。与数组的 length 属性类似。
 * isEmpty()：在 size 等于零的时候返回 true，否则返回 false。
 * keys()：将字典所包含的所有键名以数组形式返回。
 * values()：将字典所包含的所有数值以数组形式返回。
 * keyValues()：将字典中所有[键，值]对返回。
 * forEach(callbackFn)：迭代字典中所有的键值对。callbackFn 有两个参数：key 和 value。该方法可以在回调函数返回 false 时被中止（和 Array 类中的 every 方法相似）。
 * 
 * @class Map
 */
class Map { 
  constructor(toStrFn = defaultToString) { 
    this.toStrFn = toStrFn;
    this.table = {}; 
  }

  hasKey(key){
    return this.table[this.toStrFn(key)] != null;
  }

  set(key, value){
    if(key != null && value != null){
      const tableKey = this.toStrFn(key);
      this.table[tableKey] = new ValuePair(key, value); // 为了保存原有数据
      return true;
    }
    return false;
  }

  remove(key){
    if(this.hasKey(key)){
      delete this.table[this.toStrFn(key)];
      return true;
    }
    return false;
  }

  get(key){
    const valuePair = this.table[this.toStrFn(key)];
    return valuePair == null ? undefined : valuePair.value;
  }

  keyValues() { 
    // return Object.values(this.table); 
    const valuePairs = [];
    for (const k in this.table){
      if(this.hasKey(k)){
        valuePairs.push(this.table[k]);
      }
    }
    return valuePairs;
  }

  keys() { 
    // return this.keyValues().map(valuePair => valuePair.key); 
    const keys = []; 
    const valuePairs = this.keyValues(); 
    for (let i = 0; i < valuePairs.length; i++) { 
      keys.push(valuePairs[i].key);
    } 
    return keys;
  }

  values() { 
    return this.keyValues().map(valuePair => valuePair.value); 
  }

  forEach(callbackFn) { 
    const valuePairs = this.keyValues(); 
    for (let i = 0; i < valuePairs.length; i++) {
      const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
      if (result === false) { 
        break;
      } 
    } 
  }

  size() { 
    return Object.keys(this.table).length; 
  }

  isEmpty() { 
    return this.size() === 0; 
  }

  clear() { 
    this.table = {}; 
  }

  toString() { 
    if (this.isEmpty()) { 
      return ''; 
    } 
    const valuePairs = this.keyValues(); 
    let objString = `${valuePairs[0].toString()}`;
    for (let i = 1; i < valuePairs.length; i++) { 
      objString = `${objString},${valuePairs[i].toString()}`;
    } 
    return objString;
   }
}

// const map = new Map(); 
// map.set('Gandalf', 'gandalf@email.com'); 
// map.set('John', 'johnsnow@email.com'); 
// map.set('Tyrion', 'tyrion@email.com');
// console.log(map.hasKey('Gandalf'));
// console.log(map.size());
// console.log(map.keys()); 
// console.log(map.values()); 
// console.log(map.get('Tyrion'));

// map.remove('John');
// console.log(map.keys()); 
// console.log(map.values()); 
// console.log(map.keyValues());

// map.forEach((k, v) => { 
//   console.log('forEach: ', `key: ${k}, value: ${v}`); 
// });


/**
 *
 * put(key,value)：向散列表增加一个新的项（也能更新散列表）。
 * remove(key)：根据键值从散列表中移除值。
 * get(key)：返回根据键值检索到的特定的值。
 *
 * @class HashTable 离散表，哈希表
 * 
 * 散列算法的作用是尽可能快地在数据结构中找到一个值。
 * 在之前的章节中，你已经知道如果要在数据结构中获得一个值（使用 get 方法），需要迭代整个数据结构来找到它。
 * 如果使用散列函数，就知道值的具体位置，因此能够快速检索到该值。
 * 散列函数的作用是给定一个键值，然后返回值在表中的地址
 */
class HashTable { 
  constructor(toStrFn = defaultToString) { 
    this.toStrFn = toStrFn; 
    this.table = {}; 
  }

  // 获取key转换成数字，如果是可以不是数字先转换成字符串然后转换成对应的ASCII 码值
  // 为了得到比较小的数值，我们会使用 hash 值 和一个任意数做除法的余数（%）
  loseloseHashCode(key) { 
    if (typeof key === 'number') {
      return key; 
    } 
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) { 
      hash += tableKey.charCodeAt(i);
    } 
    return hash % 37; // 这可以规避操作数超过数值变量最大表示范围的风险
  }

  hashCode(key) { 
    return this.loseloseHashCode(key); 
  }

  // 把用户传过来的key转换成对应的编码数字后做为离散表的key
  put(key,value){
    if(key != null && value != null){
      const position = this.hashCode(key);
      this.table[position] = new ValuePair(key, value);
      return true;
    }
    return false;
  }

  // 根据传过来的keykey转换成对应的编码数字后就可以直接去离散表找
  get(key) { 
    const valuePair = this.table[this.hashCode(key)]; 
    return valuePair == null ? undefined : valuePair.value; 
  }

  remove(key) { 
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    if (valuePair != null) { 
      delete this.table[hash];
      return true; 
    } 
    return false; 
  }
}

const hash = new HashTable(); 
hash.put('Gandalf', 'gandalf@email.com'); 
hash.put('John', 'johnsnow@email.com'); 
hash.put('Tyrion', 'tyrion@email.com'); 
console.log(hash.hashCode('Gandalf') + ' - Gandalf'); 
console.log(hash.hashCode('John') + ' - John'); 
console.log(hash.hashCode('Tyrion') + ' - Tyrion');
console.log(hash.get('Gandalf')); // gandalf@email.com 
console.log(hash.get('Loiane')); // undefined
hash.remove('Gandalf'); 
console.log(hash.get('Gandalf'));